One of the services provided on a network is a data search service for data stored in a database. A client who wants to use the database sends a search request (query) to a database server on the network to inquire whether a desired data is in the database and receives a search result in response to the query.
In such use of the database, a search may be desired only to determine whether the database stores a particular data or not. In this case, the database server replies to the search request by returning information on the presence or absence of the requested data, rather than returning the data itself. In an exemplary situation, a user may wish to determine which technical database stores particular technical information among a plurality of technical databases. If any technical database is found to store the desired data, another request may be made for transmission of the data from that technical database storing the data.
This search approach poses some concerns: the privacy of the search request of the client at the system sending the search request, and the security of the database.
The user may not wish the details of the search request available to unauthorized persons. The search request contains information on the user's interest. For example, a company may search a technical database of a competitor. Revealing the details of that search to the competitor, such as the type of technique the company is researching, can pose a significant problem, possibly exposing the company's business strategy. On the other hand, an open database shared among companies of the same trade leads to a vigorous industry. Therefore, it would be extremely useful if a database of the competitor can be searched while the content of a search request is kept secret.
In addition, the owner of the database may wish to maintain data and database security. For example, some systems charge for data retrieval from a database. In such systems, charging for the data would be meaningless if unlimited amounts of data could be retrieved from the database in one search. Even in charge-free systems, it is desirable to avoid providing a user with excess search results, because the database itself contains information on interests or strategies of the database owner.
Several protocols have been proposed to address the issues of database access and security.
To perform a database search while hiding a list Li of data stored in a database and the value α of a data number to be searched for, one method uses a one-way hash function H. FIG. 8 describes this conventional method. Suppose that a database server Si hides a list Li={xi, 0, . . . , xi, n-1} from a client A, and the client A hides α. The database server Si then provides L′i={H(xi, 0), . . . , H(xi, n-1)} to the client A, and the client A checks whether any one matches H(α), where H(●) is a one-way hash function. In this case, neither the client A nor the database server Si needs to disclose the data numbers.
Another method as described by Naor, M. and Pinkas, B., “Oblivious Transfer and Polynomial Evaluation,” Proc. of STOC '99, uses Oblivious Polynomial Evaluation (abbreviated as OPE hereafter). This is a protocol characterized in that only a result of substituting an input into a function is received while the input is hidden.
More specifically, this method is characterized as follows. A recipient A has a secret value α, and a sender B has a secret polynomial f(x). The recipient A can know a polynomial f(α) by the OPE protocol, but obtain no information on f(β) for inputs β(≠α) other than α. On the other hand, the sender B cannot know α even after execution of the OPE protocol.
FIG. 9 describes a conventional method using OPE. First, a client A and a database server Si choose random n-order polynomials fA(x) and fSi(x), respectively. The client A obtains fSi(α) from the database server Si by OPE. The database server Si obtains fA(xi, 0), . . . , fA(xi, n-1) by OPE. The database server Si sends L′i={fSi(xi, 0)+fA(xi, 0), . . . , fSi(xi, n-1)+fA(xi, n-1)} to the client A. The client A can know whether α∈Li by computing the following equation:{tilde over (α)}=fSi(α)+fA(α)and verifying the following equation:{tilde over (α)}∈L′i According to this method, no excess information about α∈Li is exposed.
A protocol for a special form of OPE based on the Decisional Diffie-Hellman (DDH) problem is presented in Lindell, Y. and Pinkas, B., “Privacy Preserving Data Mining,” Proc. of CRYPTO2000, LNCS.
The DDH problem is a decisional problem of distinguishing between D=<g, h, ga, ha> (this form is called a “Diffie-Hellman tuple”) and R=<g, h, ga, hb> with significant probability on GF(q), where g, h∈GF(q) and a, b∈Zq are randomly chosen. Algorithms for solving this problem in polynomial time in the size of q are not known. Therefore, it is often used as means of ensuring the security of cryptography. The method using OPE in this approach is different from the method described previously in that B having the polynomial f(x) returns gf(x) (not f(x) itself) for the input α from the client A.
Thus, search methods have been proposed in which the privacy of a search request and the security of a database are taken into consideration when a database search is requested. However, these methods present numerous disadvantages.
The conventional method using a one-way hash function allows the client A to search for unlimited different items. For example, if the client A wants to know whether α′ (≠α) is included in the list Li, the client A may simply check whether H(α′) ∈L′i. By repeating this, the client A may ultimately determine the content of the list Li. That is, this method presents a problem with achieving secrecy (security) of the database.
Another conventional method using OPE requires communication in four or more passes to ensure the privacy of the search request and the security of the database, as shown in FIG. 9. Therefore, the method presents problems relating to high communication cost and complicated processing.
Thus, there is a need for a database search system and method that ensures the privacy of a search request and the security of a database with high processing efficiency. The need for such a system has heretofore remained unsatisfied.